Domino and tromino tiling [Matrix Exponentiation]

Time: O(LogN); Space: O(1); medium

We have two types of tiles: a 2x1 domino shape, and an “L” tromino shape. These shapes may be rotated.

  • XX <- domino

  • XX <- “L” tromino

  • X

Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.

Notes:

  • In a tiling, every square must be covered by a tile.

  • Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Example 1:

Input: N = 3

Output: 5

Explanation:

  • The five different ways are listed below, different letters indicates different tiles:

    1. XYZ 2. XXZ 3. XYY 4. XXY 5. XYY
   XYZ    YYZ    XZZ    XYY    XXY

Example 2:

Input: N = 1

Output: 1

Constraint:

  • N will be in range [1, 1000].

1. Dynamic Programming (Matrix Exponentiation) [O(LogN), O(1)]

[1]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def numTilings(self, N):
        """
        :type N: int
        :rtype: int
        """

        def matrix_mult(m1, m2):
            return [[sum(a * b for a, b in zip(m1_row, m2_col)) %MOD for m2_col in zip(*m2)] for m1_row in m1]

        def matrix_expo(m, pow):
            assert pow >= 0 and int(pow) == pow, "Only non-negative, integer powers allowed"
            result = [[int(i==j) for j in range(len(m))] \
                                 for i in range(len(m))]
            while pow:
                if pow % 2:
                    result = matrix_mult(result, m)
                m = matrix_mult(m, m)
                pow //= 2
            return result

        MOD = 10**9 + 7
        T = [[1, 0, 0, 1],      # #(|) = #(|) + #(=)
             [1, 0, 1, 0],      # #(「) = #(|) + #(L)
             [1, 1, 0, 0],      # #(L) = #(|) + #(「)
             [1, 1, 1, 0]]      # #(=) = #(|) + #(「) + #(L)

        return matrix_mult([[1, 0, 0, 0]], matrix_expo(T, N))[0][0]     # [a0, a(-1), a(-2), a(-3)] * T^N

[2]:

s = Solution1()

N = 3
assert s.numTilings(N) == 5
N = 1
assert s.numTilings(N) == 1

2. Dynamic Programming [O(N), O(N)]

[3]:

class Solution2(object):
    def numTilings(self, N):
        """
        :type N: int
        :rtype: int
        """
        # Prove:
        # dp[n] = dp[n-1](|) + dp[n-2](=) + 2*(dp[n-3](「」) + ... + d[0](「 = ... = 」))
        #       = dp[n-1] + dp[n-2] + dp[n-3] + dp[n-3] + 2*(dp[n-4] + ... + d[0])
        #       = dp[n-1] + dp[n-3] + (dp[n-2] + dp[n-3] + 2*(dp[n-4] + ... + d[0])
        #       = dp[n-1] + dp[n-3] + dp[n-1]
        #       = 2*dp[n-1] + dp[n-3]
        MOD = 10**9 + 7
        dp = [1, 1, 2]

        for i in range(3, N+1):
            dp[i%3] = (2 * dp[(i-1)%3]%MOD + dp[(i-3)%3])%MOD

        return dp[N%3]

[4]:

s = Solution2()

N = 3
assert s.numTilings(N) == 5
N = 1
assert s.numTilings(N) == 1